|
In order-theoretic mathematics, a series-parallel partial order is a partially ordered set built up from smaller series-parallel partial orders by two simple composition operations.〔.〕〔.〕 The series-parallel partial orders may be characterized as the N-free finite partial orders; they have order dimension at most two.〔〔.〕 They include weak orders and the reachability relationship in directed trees and directed series-parallel graphs.〔〔 The comparability graphs of series-parallel partial orders are cographs.〔〔 Series-parallel partial orders have been applied in job shop scheduling,〔.〕 machine learning of event sequencing in time series data,〔 transmission sequencing of multimedia data,〔 and throughput maximization in dataflow programming.〔 Series-parallel partial orders have also been called multitrees;〔.〕 however, that name is ambiguous: multitrees also refer to partial orders with no four-element diamond suborder〔.〕 and to other structures formed from multiple trees. ==Definition== Consider ''P'' and ''Q'', two partially ordered sets. The series composition of ''P'' and ''Q'', written ,〔 ,〔 or ,〔is the partially ordered set whose elements are the disjoint union of the elements of ''P'' and ''Q''. In , two elements ''x'' and ''y'' that both belong to ''P'' or that both belong to ''Q'' have the same order relation that they do in ''P'' or ''Q'' respectively. However, for every pair ''x'', ''y'' where ''x'' belongs to ''P'' and ''y'' belongs to ''Q'', there is an additional order relation in the series composition. Series composition is an associative operation: one can write as the series composition of three orders, without ambiguity about how to combine them pairwise, because both of the parenthesizations and describe the same partial order. However, it is not a commutative operation, because switching the roles of ''P'' and ''Q'' will produce a different partial order that reverses the order relations of pairs with one element in ''P'' and one in ''Q''.〔 The parallel composition of ''P'' and ''Q'', written ''P'' || ''Q'',〔 ,〔 or ,〔 is defined similarly, from the disjoint union of the elements in ''P'' and the elements in ''Q'', with pairs of elements that both belong to ''P'' or both to ''Q'' having the same order as they do in ''P'' or ''Q'' respectively. In ''P'' || ''Q'', a pair ''x'', ''y'' is incomparable whenever ''x'' belongs to ''P'' and ''y'' belongs to ''Q''. Parallel composition is both commutative and associative.〔 The class of series-parallel partial orders is the set of partial orders that can be built up from single-element partial orders using these two operations. Equivalently, it is the smallest set of partial orders that includes the single-element partial order and is closed under the series and parallel composition operations.〔〔 A weak order is the series parallel partial order obtained from a sequence of composition operations in which all of the parallel compositions are performed first, and then the results of these compositions are combined using only series compositions.〔 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Series-parallel partial order」の詳細全文を読む スポンサード リンク
|